package fun.ticsmyc.question.dp;

import java.util.Arrays;

/**
 * @author Ticsmyc
 * @date 2021-03-21 11:59
 */
public class 戳气球 {

    /*********************** dp *************************************/
    public int maxCoins(int[] nums) {
        //处理边界
        int[] arr = new int[nums.length+2];
        arr[0]=1;
        arr[arr.length-1]=1;
        for(int i=0;i<nums.length;++i){
            arr[i+1]=nums[i];
        }
        //dp表
        int[][] dp = new int[arr.length][arr.length];

        //直接填表
        for(int left = dp.length-3;left >=0;--left){
            for(int right = left+2;right<dp[0].length;++right){
                //戳哪个
                int max =0;
                for(int i=left+1;i<right;++i){
                    max = Math.max(max, arr[left]*arr[right]*arr[i] + dp[left][i]+dp[i][right]);
                }
                dp[left][right] = max;
            }
        }
        return dp[0][dp.length-1];
    }

    /***************************** 递归+备忘录解法 *************************************/
    public int maxCoins2(int[] nums) {
        //处理边界
        int[] arr = new int[nums.length+2];
        arr[0]=1;
        arr[arr.length-1]=1;
        for(int i=0;i<nums.length;++i){
            arr[i+1]=nums[i];
        }
        //备忘录
        int[][] dp = new int[arr.length][arr.length];
        for(int[] d: dp){
            Arrays.fill(d,-1);
        }
        return dfs(arr,dp,0,arr.length-1);
    }

    /**
     * 从最后一个气球开始， 构建整个数组
     * left  right为最后一个气球的两边
     */
    public int dfs(int[] arr,int[][] dp,int left, int right){
        //备忘录
        if(dp[left][right] !=-1){
            return dp[left][right];
        }

        int max =0;
        for(int i=left+1; i<right;++i){
            //戳i
            max = Math.max(arr[left]*arr[right]*arr[i] + dfs(arr,dp,left,i) + dfs(arr,dp,i,right) , max);
        }
        dp[left][right] = max;
        return max;
    }
}
